#include<iostream>
using namespace std;
static int Max = 0;
class TreeNode {
public:
	char Data;
	int n;
	int m;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char ch = '0') {
		Data = ch;
		left = right = NULL;
	}
};
class Tree {
public:
	TreeNode* tmp;
	Tree() {
		Init(tmp);
	}
	void Init(TreeNode*&p) {
		char ch;
		cin >> ch;
		if (ch == '0') {
			p = NULL;
		}
		else {
			p = new TreeNode(ch);
			Init(p->left);
			Init(p->right);
		}
	}
	void made(TreeNode* p, int* a, int& n) {
		if (p == NULL) {
			return;
		}
		p->n = a[n++];
		made(p->left, a, n);
		made(p->right, a, n);
	}
	void my(TreeNode* p) {
		if (p == NULL) {
			return;
		}
		if (p == tmp) {
			p->m = p->n;
		}
		if (p->left != NULL) {
			p->left->m = p->m + p->left->n;
		}
		if (p->right != NULL) {
			p->right->m = p->m + p->right->n;
		}
		my(p->left);
		my(p->right);
	}
	void find(TreeNode* p) {
		if (p == NULL) {
			return;
		}
		if (p->left == NULL && p->right == NULL) {
			if (p->m > Max) {
				Max = p->m;
			}
		}
		find(p->left);
		find(p->right);
	}
};
int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		Max = 0;
		Tree T;
		int n;
		cin >> n;
		int* a = new int[n];
		for (int j = 0; j < n; j++) {
			cin >> a[j];
		}
		int k = 0;
		T.made(T.tmp, a, k);
		T.my(T.tmp);
		T.find(T.tmp);
		cout<<Max<<endl;
	}
	return 0;
}